package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 19:54 2020/8/26
 * @Description 最长相同路径
    给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
    注意：两个节点之间的路径长度由它们之间的边数表示。
 */

public class LongestUnivaluePath {

    int ans = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return ans;
    }

    private int helper(TreeNode root) {
        if (root == null) return 0;
        int maxPath = 0;
        int left = helper(root.left);
        int right = helper(root.right);
        // 两边匹配的情况
        if (root.left != null && root.left.val == root.val && root.right != null && root.right.val == root.val) {
            ans = Math.max(ans, left + right + 2);
        }
        // 单边匹配，那ans就更新单边最大  无论是单边还是双边匹配都要返回maxPath也就是其中最长的一条路径
        if (root.left != null && root.left.val == root.val) {
            maxPath = left + 1;
        }
        if (root.right != null && root.right.val == root.val) {
            maxPath = Math.max(maxPath, right + 1);
        }
        ans = Math.max(ans, maxPath);
        return maxPath;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
